package hot100;

public class longestPalindromeSubseq {
    public int longestPalindromeSubseq(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[][] dp = new int[n][n];

        int res = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (chars[i] == chars[j]) {
                    if (j - i < 1) dp[i][j] = 1;
                    else if (j - i == 1) dp[i][j] = 2;
                    else dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    if (j - i < 1) dp[i][j] = 1;
                    else if (j - i == 1) dp[i][j] = 1;
                    else {
                        dp[i][j] = Math.max(dp[i + 1][j - 1]
                                ,Math.max(dp[i + 1][j],dp[i][j - 1]));//不相等，则顺延
                    }
                }

                res = Math.max(res,dp[i][j]);
            }
        }

        return res;
    }
}
